#include <stdio.h>  
#include <stdlib.h>  
  
#define MAX_VERTICES 100  
  
int graph[MAX_VERTICES][MAX_VERTICES];  
int dist[MAX_VERTICES];  
int visited[MAX_VERTICES];  
  
int floydWarshall(int n) {  
    int i, j, k;  
    for (i = 0; i < n; i++) {  
        for (j = 0; j < n; j++) {  
            dist[j] = dist[j] + graph[i][j];  
        }  
    }  
    for (k = 0; k < n; k++) {  
        for (i = 0; i < n; i++) {  
            for (j = 0; j < n; j++) {  
                if (dist[i] + graph[i][k] + graph[k][j] < dist[j]) {  
                    dist[j] = dist[i] + graph[i][k] + graph[k][j];  
                }  
            }  
        }  
    }  
    return n;  
}  
  
int main() {  
    int n, m, i, j, u, v, w;  
    printf("Enter the number of vertices: ");  
    scanf("%d", &n);  
    printf("Enter the number of edges: ");  
    scanf("%d", &m);  
    for (i = 0; i < m; i++) {  
        printf("Enter the source vertex, destination vertex and weight of edge %d: ", i + 1);  
        scanf("%d %d %d", &u, &v, &w);  
        graph[u][v] = w;  
    }  
    for (i = 0; i < n; i++) {  
        for (j = 0; j < n; j++) {  
            if (i == j) {  
                dist[j] = 0;  
            } else {  
                dist[j] = INT_MAX;  
            }  
        }  
        visited[i] = 1;  
        floydWarshall(n);  
        visited[i] = 0;  
    }  
    printf("The shortest distance from vertex %d to vertex %d is %d\n", 0, n - 1, dist[n - 1]);  
    return 0;  
}